import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/23 22:33
 * @description 01 字典树
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        Solution solution = new Solution();
        System.out.println(solution.findMaximumXOR(nums));
    }

    /**
     * 01 字典树的根节点
     */
    Trie root = new Trie();
    /**
     * 最高位的二进制位编号为 30
     */
    static final int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        int x = 0;
        for (int i = 1; i < n; ++i) {
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            root.insert(nums[i - 1]);
            // 将 nums[i] 看作 ai，找出最大的 x 更新答案
            x = Math.max(x, root.getMaxXor(nums[i]));
        }
        return x;
    }


}

class Trie {
    static final int L = 30;

    Trie[] children = new Trie[2];

    public void insert(int val) {
        Trie node = this;
        for (int i = L; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new Trie();
            }
            node = node.children[bit];
        }
    }

    public int getMaxXor(int val) {
        int ans = 0;
        Trie node = this;
        for (int i = L; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node.children[bit ^ 1] != null) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node.children[bit];
        }
        return ans;
    }
}
